class Solution
{
public:
    int numIslands(vector<vector<char>> &grid)
    {
        int islandCount = 0;
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == '1')
                {
                    ++islandCount;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    grid[i][j] = 0;
                    while (!q.empty())
                    {
                        auto [x, y] = q.front();
                        q.pop();
                        if (x > 0 && grid[x - 1][y] == '1')
                        {
                            grid[x - 1][y] = 0;
                            q.push({x - 1, y});
                        }
                        if (y > 0 && grid[x][y - 1] == '1')
                        {
                            grid[x][y - 1] = 0;
                            q.push({x, y - 1});
                        }
                        if (x < m - 1 && grid[x + 1][y] == '1')
                        {
                            grid[x + 1][y] = 0;
                            q.push({x + 1, y});
                        }
                        if (y < n - 1 && grid[x][y + 1] == '1')
                        {
                            grid[x][y + 1] = 0;
                            q.push({x, y + 1});
                        }
                    }
                }
            }
        }
        return islandCount;
    }
};